﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm.Hard_1001_GridIllumination
{
    class MainProject
    {
        static void Main(string[] args)
        {
            int[][] lamps = new int[][] {
                new int[]{0,0 },
                new int[]{4,4 },
            };

            int[][] queries = new int[][] {
                new int[]{1,1 },
                new int[]{1,0},
            };
            int[] res = GridIllumination(5, lamps, queries);
            foreach (var item in res)
            {
                Console.WriteLine(item);
            }
            Console.ReadKey();
        }
        public static int[] GridIllumination(int n, int[][] lamps, int[][] queries)
        {
            //抽象成四层看(借助暴力破解法理解)
            Dictionary<int, int> row = new Dictionary<int, int>();
            Dictionary<int, int> col = new Dictionary<int, int>();
            Dictionary<int, int> diagonal = new Dictionary<int, int>();
            Dictionary<int, int> antiDiagonal = new Dictionary<int, int>();
            ISet<long> points = new HashSet<long>();

            foreach (var lamp in lamps)
            {
                if (!points.Add(Hash(lamp[0], lamp[1]))) continue;

                if (!row.ContainsKey(lamp[0]))
                {
                    row.Add(lamp[0], 0);
                }
                row[lamp[0]]++;

                if (!col.ContainsKey(lamp[1]))
                {
                    col.Add(lamp[1], 0);
                }
                col[lamp[1]]++;

                if (!diagonal.ContainsKey(lamp[0] - lamp[1]))
                {
                    diagonal.Add(lamp[0] - lamp[1], 0);
                }
                diagonal[lamp[0] - lamp[1]]++;

                if (!antiDiagonal.ContainsKey(lamp[1] + lamp[0]))
                {
                    antiDiagonal.Add(lamp[0] + lamp[1], 0);
                }
                antiDiagonal[lamp[1] + lamp[0]]++;
            }
            int[] res = new int[queries.Length];

            for (int i = 0; i < queries.Length; i++)
            {
                int x = queries[i][0];
                int y = queries[i][1];
                if (row.ContainsKey(x) && row[x] > 0)
                    res[i] = 1;
                else if (col.ContainsKey(y) && col[y] > 0)
                    res[i] = 1;
                else if (diagonal.ContainsKey(x - y) && diagonal[x - y] > 0)
                    res[i] = 1;
                else if (antiDiagonal.ContainsKey(x + y) && antiDiagonal[x + y] > 0)
                    res[i] = 1;

                for (int j = x - 1; j <= x + 1; j++)
                {
                    for (int k = y - 1; k <= y + 1; k++)
                    {
                        if (j < 0 || k < 0 || j >= n || k >= n)
                        {
                            continue;
                        }
                        if (points.Remove(Hash(j, k)))
                        {
                            row[j]--;
                            if (row[j] == 0)
                            {
                                row.Remove(row[j]);
                            }
                            col[k]--;
                            if (col[k] == 0)
                            {
                                col.Remove(col[k]);
                            }
                            diagonal[j - k]--;
                            if (diagonal[j - k] == 0)
                            {
                                diagonal.Remove(diagonal[j - k]);
                            }
                            antiDiagonal[j + k]--;
                            if (antiDiagonal[j + k] == 0)
                            {
                                antiDiagonal.Remove(antiDiagonal[j + k]);
                            }
                        }
                    }
                }
            }
            return res;
        }
        public static long Hash(int x, int y)
        {
            //怎么知道就是会唯一的(原理上和x*1000+y是一样的)
            return (long)x + ((long)y << 32);
        }


        /// <summary>
        /// 超时超内存
        /// </summary>
        /// <param name="n"></param>
        /// <param name="lamps"></param>
        /// <param name="queries"></param>
        /// <returns></returns>
        public static int[] GridIllumination1(int n, int[][] lamps, int[][] queries)
        {
            int[][] grids = new int[n][];

            int[] res = new int[queries.Length];
            //初始化grids数组
            for (int i = 0; i < n; i++)
            {
                grids[i] = new int[n];
               
            }
          
            int a = 3;
            //打开所有亮灯
            for (int i = 0; i < lamps.Length; i++)
            {
                ControlLamp(grids, lamps[i]);
            }

            List<int> lampID = new List<int>();
            //查找灯，并且关闭区域内所有灯及其影响
            for (int i = 0; i < queries.Length; i++)
            {
                int x = queries[i][0];
                int y = queries[i][1];
                res[i] = grids[x][y] >= 1 ? 1 : 0;

                if (lampID.Contains(i)) continue;

                //先获得结果

                int[][] wait = new int[9][];
                int l = 0;
                for (int j = -1; j <= 1; j++)
                {
                    for (int k = -1; k <= 1; k++)
                    {
                        
                        x += j;
                        y += k;
                        if (x < 0 || y < 0 || x >= n || y >= n)
                        {
                            //啥也不干
                        }
                        else
                        {
                            wait[l] = new int[] { x, y };
                            l++;
                        }
                        x = queries[i][0];
                        y = queries[i][1];
                    }    
                }

                //查找有没有灯泡
                for (int j = 0; j < lamps.Length; j++)
                {
                    for (int k = 0; k < wait.Length; k++)
                    {
                        if (wait[k]==null) continue;

                        if (lamps[j][0] == wait[k][0]&& lamps[j][1] == wait[k][1])
                        {
                            if (!lampID.Contains(j))
                            {
                                lampID.Add(j);
                                ControlLamp(grids, lamps[j], -1);
                            }
                        }
                    }
                }
            }

            //重复上一步骤
            return res;

        }

        private static void ControlLamp(int[][] grids, int[] lamp, int status = 1)
        {
            //if (grids.Length < lamp.Length) return;

            int[][] temp = new int[grids.Length][];
            for (int i = 0; i < grids.Length; i++)
            {
                temp[i] = new int[grids.Length];
                for (int j = 0; j < grids.Length; j++)
                {
                    temp[i][j] = 0;
                }
            }

            //横
            for (int i = 0; i < grids.Length; i++)
            {
                if (temp[lamp[0]][i] != status)
                    temp[lamp[0]][i] = status;
            }
            //竖
            for (int i = 0; i < grids.Length; i++)
            {
                if (temp[i][lamp[1]] != status)
                    temp[i][lamp[1]] = status;
            }
            int x = lamp[0];
            int y = lamp[1];
            //左上
            while (x >= 0 && y >= 0)
            {
                if (temp[x][y] != status)
                    temp[x][y] = status;
                x--;
                y--;
            }
            x = lamp[0];
            y = lamp[1];
            //右上
            while (x < grids.Length && y >= 0)
            {
                if (temp[x][y] != status)
                    temp[x][y] = status;
                x++;
                y--;
            }
            x = lamp[0];
            y = lamp[1];
            //左下
            while (x >= 0 && y < grids.Length)
            {
                if (temp[x][y] != status)
                    temp[x][y] = status;
                x--;
                y++;
            }
            x = lamp[0];
            y = lamp[1];
            //右下
            while (x < grids.Length && y < grids.Length)
            {
                if (temp[x][y] != status)
                    temp[x][y] = status;
                x++;
                y++;
            }

            for (int i = 0; i < grids.Length; i++)
            {
                for (int j = 0; j < grids.Length; j++)
                {
                    grids[i][j] += temp[i][j];
                }
            }
        }
    }
}
